home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Games / Xconq 7.1.0 / src / xconq-7.1.0 / kernel / mkunits.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-07-07  |  23.5 KB  |  817 lines  |  [TEXT/R*ch]
  1. /* Unit generation for Xconq.
  2.    Copyright (C) 1986, 1987, 1988, 1989, 1991, 1992, 1993, 1994, 1995
  3.    Stanley T. Shebs.
  4.  
  5. Xconq is free software; you can redistribute it and/or modify
  6. it under the terms of the GNU General Public License as published by
  7. the Free Software Foundation; either version 2, or (at your option)
  8. any later version.  See the file COPYING.  */
  9.  
  10. #include "conq.h"
  11.  
  12. static void set_people_on_side PARAMS ((int x, int y));
  13. static void expand_country PARAMS ((int x, int y));
  14. static int country_is_complete PARAMS ((Side *side, int runs));
  15. static int average_numunits PARAMS ((int u));
  16. static void count_cells PARAMS ((int x, int y));
  17. static int good_place PARAMS ((int cx, int cy));
  18. static void find_a_place PARAMS ((Side *side));
  19. static int valid_unit_place PARAMS ((int x, int y));
  20. static int possible_unit_place PARAMS ((int x, int y));
  21. static int find_unit_place PARAMS ((int u, int cx, int cy, int *xp, int *yp));
  22. static void mung_terrain PARAMS ((int x, int y, int u));
  23. static Unit *find_occupant_place PARAMS ((Side *side, int u, int x0, int y0));
  24. static int at_country_units_max PARAMS ((Side *side, int u));
  25.  
  26. /* Tmp array for counting terrain. */
  27.  
  28. static int *numcells;
  29.  
  30. static int *favorite;
  31.  
  32. static int *totnumcells;
  33.  
  34. /* This is the number of country placements that could not be found to meet
  35.    all the constraints. */
  36.  
  37. static int badcountryplaces = 0;
  38.  
  39. /* This says whether terrain alteration is permissible to make country
  40.    placements work.  This only happens when normal placement starts to fail. */
  41.  
  42. static int mungterrain;
  43.  
  44. static int baseradius;
  45.  
  46. static int tmpradius;
  47.  
  48. static int curmindistance;
  49. static int curmaxdistance;
  50.  
  51. static int sideprogress;
  52. int sidedeltahalf;
  53.  
  54. static int growth;
  55.  
  56. /* Set the people inside the country to be on the country's side.
  57.    Flip a coin along the edges, to make the border more interesting.
  58.    Also don't always overwrite existing people. */
  59.  
  60. static void
  61. set_people_on_side(x, y)
  62. int x, y;
  63. {
  64.     if ((distance(tmpside->startx, tmpside->starty, x, y) <= tmpradius
  65.          || flip_coin())
  66.         && probability(t_country_people(terrain_at(x, y)))
  67.         && (people_side_at(x, y) == NOBODY || flip_coin())) {
  68.     set_people_side_at(x, y, side_number(tmpside));
  69.     }
  70. }
  71.  
  72. /* Expand a country into the given cell. */
  73.  
  74. static void
  75. expand_country(x, y)
  76. int x, y;
  77. {
  78.     int u, t = terrain_at(x, y), ours, theirs, prob;
  79.     Unit *unit;
  80.     
  81.     if (people_side_at(x, y) == NOBODY) {
  82.     prob = t_country_growth(t);
  83.     } else {
  84.     prob = t_country_takeover(t);
  85.     }
  86.     if (probability(prob)) {
  87.     /* Claim the cell, attempt to own it. */
  88.     ours = theirs = FALSE;
  89.     if (unit_at(x, y) == NULL) {
  90.         /* If completely empty, we claim it. */
  91.         ours = TRUE;
  92.         for_all_unit_types(u) {
  93.             tmputype = u;
  94.         if (xrandom(10000) < u_unit_growth(u)
  95.             && !at_country_units_max(tmpside, u)
  96.             && probability(ut_favored(u, t))
  97.             && valid_unit_place(x, y)) {
  98.             unit = create_unit(u, TRUE);
  99.             if (unit != NULL) {
  100.             set_unit_side(unit, tmpside);
  101.             set_unit_origside(unit, tmpside);
  102.             init_supply(unit);
  103.             enter_cell(unit, x, y);
  104.                 break;
  105.             }
  106.         }
  107.         if (xrandom(10000) < u_indep_growth(u)
  108.             && !at_country_units_max(tmpside, u)
  109.             && probability(ut_favored(u, t))
  110.             && valid_unit_place(x, y)) {
  111.             unit = create_unit(u, TRUE);
  112.             if (unit != NULL) {
  113.             init_supply(unit);
  114.             enter_cell(unit, x, y);
  115.                 break;
  116.             }
  117.         }
  118.         }
  119.     } else {
  120.         /* Somebody is here already. */
  121.         for_all_stack(x, y, unit) {
  122.         if (unit->side != tmpside) {
  123.             if (unit->side != NULL) {
  124.             /* Maybe take over another side's unit. */
  125.             if (xrandom(10000) < u_unit_takeover(unit->type)
  126.                 && !at_country_units_max(tmpside, unit->type)
  127.                 ) {
  128.                 set_unit_side(unit, tmpside);
  129.                 set_unit_origside(unit, tmpside);
  130.                 ours = TRUE;
  131.             } else {
  132.                 /* Indicate that we don't have possession of every
  133.                    unit in this cell. */
  134.                 theirs = TRUE;
  135.             }
  136.             } else {
  137.             /* Maybe take over an independent unit. */
  138.             if (xrandom(10000) < u_indep_takeover(unit->type)
  139.                 && !at_country_units_max(tmpside, unit->type)
  140.                 ) {
  141.                 set_unit_side(unit, tmpside);
  142.                 set_unit_origside(unit, tmpside);
  143.                 ours = TRUE;
  144.             }
  145.             }
  146.         }
  147.         }
  148.     }
  149.     /* If cell is claimed, and has no opposition, then country gets it. */
  150.     if (ours && !theirs && probability(t_country_people(t))) {
  151.         set_people_side_at(x, y, side_number(tmpside));
  152.     }
  153.     /* Count this cell as one we expanded into. */
  154.     ++growth;
  155.     }
  156.     /* The cell should become known even if not occupied, but we can't
  157.        do that here because view structures don't exist yet. */
  158. }
  159.  
  160. #define announce_unit_progress(n) \
  161.   announce_progress(sideprogress + sidedeltahalf + (sidedeltahalf * (n)) / totnumtodo)
  162.  
  163. /* Place all the units belonging to countries. */
  164.  
  165. int
  166. make_countries(calls, runs)
  167. int calls, runs;
  168. {
  169.     int x0, y0, u, t, i, tot, x, y;
  170.     int advantage, sideadvantage, favor, x1, y1, dir;
  171.     int canbeinopen[MAXUTYPES];  /* true if type need not be occ at start */
  172.     int numtodo[MAXUTYPES], numindeptodo[MAXUTYPES], totnumtodo, totnumdone;
  173.     int numleft[MAXUTYPES], numindepleft[MAXUTYPES], totleft, numlisted, numfails;
  174.     int checkmins = FALSE;
  175.     int dopeoplesides = FALSE, dopeopleindeps = FALSE;
  176.     int maxradius;
  177.     int numdone = 0;
  178.     Unit *unit, *transport;
  179.     Side *side;
  180.     char tmpbuf2[BUFSIZE];
  181.  
  182.     /* Run this always, unless something important is missing. */
  183.     if (!terrain_defined())
  184.       return FALSE;
  185.     /* Calculate whether the minimum required terrain types are present. */
  186.     totnumcells = (int *) xmalloc(numttypes * sizeof(int));
  187.     for_all_terrain_types(t) {
  188.         if (t_country_min(t) > 0)
  189.           checkmins = TRUE;
  190.     }
  191.     if (checkmins) {
  192.         /* Edge cells are useless for country placement. */
  193.         for_all_interior_cells(x, y) {
  194.             ++totnumcells[terrain_at(x, y)];
  195.         }
  196.         for_all_terrain_types(t) {
  197.             if (t_country_min(t) * numsides > totnumcells[t]) {
  198.                 init_warning("Not enough %s for all %d sides",
  199.                  t_type_name(t), numsides);
  200.                 /* Don't error out, might be extenuating circumstances. */
  201.             }
  202.         }
  203.     }
  204.     announce_lengthy_process("Making countries");
  205.     /* Precompute some important info */
  206.     numcells = (int *) xmalloc(numttypes * sizeof(int));
  207.     favorite = (int *) xmalloc(numutypes * sizeof(int));
  208.     tot = 0;
  209.     for_all_unit_types(u) {
  210.     canbeinopen[u] = FALSE;
  211.     favorite[u] = NONTTYPE;
  212.     favor = 0;
  213.     for_all_terrain_types(t) {
  214.         if (ut_favored(u, t) > 0)
  215.           canbeinopen[u] = TRUE;
  216.         if (ut_favored(u, t) > favor) {
  217.         favorite[u] = t;
  218.         favor = ut_favored(u, t);
  219.         }
  220.     }
  221.     if (canbeinopen[u]) {
  222.         tot += u_start_with(u) + u_indep_near_start(u);
  223.     }
  224.     }
  225.     /* Make space for people sides if we're going to have any. */
  226.     if (!people_sides_defined()) {
  227.     for_all_terrain_types(t) {
  228.         if (t_country_people(t) > 0)
  229.           dopeoplesides = TRUE;
  230.         if (t_indep_people(t) > 0)
  231.           dopeopleindeps = TRUE;
  232.     }
  233.     if (dopeoplesides || dopeopleindeps) {
  234.         allocate_area_people_sides();
  235.     }
  236.     }
  237.     if (g_radius_min() <= 0) {
  238.     /* If no radius specified, pick something plausible. */
  239.     baseradius = max(1, isqrt(3 * tot) / 2);
  240.     } else {
  241.     baseradius = g_radius_min();
  242.     }
  243.     curmindistance = g_separation_min();
  244.     curmaxdistance = g_separation_max();
  245.     badcountryplaces = 0;
  246.     for_all_sides(side) {
  247.     sideprogress = (100 * numdone++) / numsides;
  248.     sidedeltahalf = (100 / numsides) / 2;
  249.     announce_progress(sideprogress);
  250.     if (!country_is_complete(side, runs)) {
  251.         sideadvantage = max(1, side->advantage);
  252.         advantage = (side->player ? side->player->advantage : sideadvantage);
  253.         tmpradius = baseradius;
  254.         if (advantage > 1)
  255.           tmpradius = (baseradius * isqrt(advantage * 100) + 9) / 10;
  256.         /* Discover or generate the country's center. */
  257.         mungterrain = FALSE;
  258.         find_a_place(side);
  259.         x0 = side->startx;  y0 = side->starty;
  260.         Dprintf("%s starts around %d,%d\n", side_desig(side), x0, y0);
  261.         announce_progress(sideprogress + sidedeltahalf);
  262.         totnumtodo = totnumdone = 0;
  263.         /* Calculate how many units of each type we will get, both the ones
  264.            that belong to the side, and the independents nearby. */
  265.         for_all_unit_types(u) {
  266.         numtodo[u] = numindeptodo[u] = 0;
  267.         if (type_allowed_on_side(u, side)) {
  268.             if (runs > 0) {
  269.             /* If the side is just coming into the game, give it an
  270.                average number of each type that the existing sides
  271.                started out with, so that the new side has some parity. */
  272.             if (u_start_with(u) > 0 || u_indep_near_start(u) > 0)
  273.               numtodo[u] = (average_numunits(u) * advantage) / sideadvantage;
  274.             } else {
  275.             numtodo[u] = (u_start_with(u) * advantage) / sideadvantage;
  276.             }
  277.             totnumtodo += numtodo[u];
  278.         }
  279.         if (type_allowed_on_side(u, NULL)) {
  280.             numindeptodo[u] = (u_indep_near_start(u) * advantage) / sideadvantage;
  281.             totnumtodo += numindeptodo[u];
  282.         }
  283.         numleft[u] = numindepleft[u] = 0;
  284.         }
  285.         /* First do units actually belonging to the side initially. */
  286.         for_all_unit_types(u) {
  287.         if (canbeinopen[u]) {
  288.             for (i = 0; i < numtodo[u]; ++i) {
  289.             if (find_unit_place(u, x0, y0, &x, &y)) {
  290.                 unit = create_unit(u, TRUE);
  291.                 if (unit != NULL) {
  292.                 set_unit_side(unit, side);
  293.                 set_unit_origside(unit, side);
  294.                 init_supply(unit);
  295.                 enter_cell(unit, x, y);
  296.                    announce_unit_progress(++totnumdone);
  297.                 }
  298.             } else {
  299.                 /* If can't find places for this type, give up. */
  300.                     numleft[u] = numtodo[u] - i;
  301.                 break;
  302.             }
  303.             }
  304.         }
  305.         }
  306.         /* Now do independents in the initial country area. */
  307.         for_all_unit_types(u) {
  308.         for (i = 0; i < numindeptodo[u]; ++i) {
  309.             if (find_unit_place(u, x0, y0, &x, &y)) {
  310.             unit = create_unit(u, TRUE);
  311.             if (unit != NULL) {
  312.                 init_supply(unit);
  313.                 enter_cell(unit, x, y);
  314.                 announce_unit_progress(++totnumdone);
  315.             }
  316.             } else {
  317.             /* If can't find places for this type, give up. */
  318.             numindepleft[u] = numindeptodo[u] - i;
  319.             break;
  320.             }
  321.         }
  322.         }
  323.         /* Now do units that have to be occupants.  Note that if occupants
  324.            are allowed in independent units, then they might be
  325.            placed in an independent rather than an owned unit. */
  326.         for_all_unit_types(u) {
  327.         if (!canbeinopen[u]) {
  328.             for (i = 0; i < numtodo[u]; ++i) {
  329.             if ((transport = find_occupant_place(side, u, x0, y0))
  330.                 != NULL) {
  331.                 unit = create_unit(u, TRUE);
  332.                 if (unit != NULL) {
  333.                 set_unit_side(unit, side);
  334.                 set_unit_origside(unit, side);
  335.                 init_supply(unit);
  336.                 enter_transport(unit, transport);
  337.                    announce_unit_progress(++totnumdone);
  338.                 }
  339.             } else {
  340.                    numleft[u] = numtodo[u] - i;
  341.                 break;
  342.             }
  343.             }
  344.         }
  345.         }
  346.         /* Now warn about what couldn't be placed. */
  347.         totleft = numlisted = numfails = 0;
  348.         tmpbuf2[0] = '\0';
  349.         for_all_unit_types(u) {
  350.         totleft += numleft[u];
  351.         if (numleft[u] > 0 && numlisted < 5) {
  352.             ++numfails;
  353.             strcat(tmpbuf2, " ");
  354.             strcat(tmpbuf2, u_type_name(u));
  355.         }
  356.         }
  357.         if (totleft > 0) {
  358.         char tmpbuf3[BUFSIZE];
  359.  
  360.         init_warning("could not put %d units in %s country (%s%s)",
  361.                  totleft, shortest_side_title(side, tmpbuf3),
  362.                  tmpbuf2, (numfails >= 5 ? " etc" : ""));
  363.         }
  364.     }
  365.     /* Now set the side of the people in this country. */
  366.     tmpside = side;
  367.     apply_to_area(side->startx, side->starty, tmpradius + 1,
  368.               set_people_on_side);
  369.     /* Make sure each unit has people there, if allowed at all. */
  370.     for_all_side_units(side, unit) {
  371.         if (inside_area(unit->x, unit->y)
  372.             && t_country_people(terrain_at(unit->x, unit->y)) > 0) {
  373.         set_people_side_at(unit->x, unit->y, side_number(side));
  374.         }
  375.     }
  376.     }
  377.     finish_lengthy_process();
  378.     /* Grow each country out to a maximum radius. */
  379.     announce_lengthy_process("Growing countries");
  380.     maxradius = min(area.width, g_radius_max());
  381.     for_all_sides(side)
  382.       side->finalradius = maxradius;
  383.     for (i = baseradius; i < maxradius; ++i) {
  384.         announce_progress((100 * (i - baseradius)) / (maxradius - baseradius));
  385.     for_all_sides(side) {
  386.         /* If side still allowed to grow, expand it. */
  387.         if (side->finalradius == maxradius) {
  388.             tmpside = side;
  389.             growth = 0;
  390.             apply_to_ring(side->startx, side->starty, i - 2, i,
  391.                   expand_country);
  392.         /* If no actual growth happened in a step, the country
  393.            might have reached its natural size. */
  394.             if (growth == 0 && probability(g_growth_stop())) {
  395.             side->finalradius = i;
  396.             }
  397.         }
  398.     }
  399.     }
  400.     /* Do a couple "consolidation" steps to fill in "jaggies". */
  401.     for (i = 0; i < 2; ++i) {
  402.     for_all_sides(side) {
  403.         tmpside = side;
  404.         apply_to_ring(side->startx, side->starty,
  405.               baseradius, side->finalradius - 1,
  406.               expand_country);
  407.     }
  408.     }
  409.     /* Also remove isolated populations surrounded by one other side. */
  410.     if (people_sides_defined()) {
  411.     for_all_interior_cells(x, y) {
  412.         int pop, pop2, majoritypop;
  413.         
  414.         if ((pop = people_side_at(x, y)) != NOBODY) {
  415.         majoritypop = NOBODY;
  416.         for_all_directions(dir) {
  417.             if (interior_point_in_dir(x, y, dir, &x1, &y1)) {
  418.             if ((pop2 = people_side_at(x1, y1)) == pop)
  419.               goto nextcell;
  420.             if (majoritypop == NOBODY) {
  421.                 majoritypop = pop2;
  422.             } else {
  423.                 if (pop2 != majoritypop)
  424.                   goto nextcell;
  425.             }
  426.             }
  427.         }
  428.         if (majoritypop != NOBODY) {
  429.             set_people_side_at(x, y, majoritypop);
  430.         }
  431.         }
  432.       nextcell:
  433.         pop = pop;  /* a dummy statement */
  434.     }
  435.     }
  436.     finish_lengthy_process();
  437.     /* Warn about any difficulties encountered. */
  438.     if (badcountryplaces > 0) {
  439.         init_warning("%d of %d sides have undesirable locations",
  440.              badcountryplaces, numsides);
  441.     }
  442.     return TRUE;
  443. }
  444.  
  445. /* Test to see whether the side's pre-existing setup already suffices
  446.    as a country in this game. */
  447.  
  448. static int
  449. country_is_complete(side, runs)
  450. Side *side;
  451. int runs;
  452. {
  453.     int u, totunits, numunits[MAXUTYPES];
  454.     Unit *unit;
  455.     int sideadvantage = max(1, side->advantage);
  456.     int advantage = (side->player ? side->player->advantage : sideadvantage);
  457.  
  458.     /* If side no longer in game, then we don't want to return country synth on it. */
  459.     if (!side->ingame)
  460.       return TRUE;
  461.     totunits = 0;
  462.     for_all_unit_types(u)
  463.       numunits[u] = 0;
  464.     /* Count up all and only the completed and present units. */
  465.     for_all_side_units(side, unit) {
  466.         if (in_play(unit)) {
  467.         ++totunits;
  468.         ++numunits[unit->type];
  469.     }
  470.     }
  471.     /* See if we're re-running side generation for the benefit of adding a
  472.        new side, use the total counts of units to distinguish the new side
  473.        from the old sides. */ 
  474.     if (runs > 0)
  475.       return (totunits > 0);
  476.     for_all_unit_types(u) {
  477.     if (numunits[u] < ((u_start_with(u) * advantage) / sideadvantage))
  478.       return FALSE;
  479.     }
  480.     return TRUE;
  481. }
  482.  
  483. /* Compute the average number of units of a given type that are currently
  484.    in the game. */
  485.  
  486. static int
  487. average_numunits(u)
  488. int u;
  489. {
  490.     int count = 0, nsides = 0;
  491.     Unit *unit;
  492.     Side *side;
  493.  
  494.     for_all_sides(side) {
  495.     if (side->ingame) {
  496.         ++nsides;
  497.         for_all_side_units(side, unit) {
  498.         if (in_play(unit) && unit->type == u)
  499.           ++count;
  500.         }
  501.     }
  502.     }
  503.     return (count / (nsides > 1 ? nsides - 1 : 1));
  504. }
  505.  
  506. /* Count the cell as being of a particular type. */
  507.  
  508. static void
  509. count_cells(x, y)
  510. int x, y;
  511. {
  512.     ++numcells[terrain_at(x, y)];
  513. }
  514.  
  515. /* Test whether a given location is desirable for a country.  It should be
  516.    in the right distance range from other countries, and have enough of
  517.    the right sorts of terrain. */
  518.  
  519. static int
  520. good_place(cx, cy)
  521. int cx, cy;
  522. {
  523.     int toofar = TRUE, notfirst = FALSE, px, py, dist, t;
  524.     Side *side;
  525.  
  526.     /* Check the candidate position against the other countries' positions. */
  527.     for_all_sides(side) {
  528.     px = side->startx;  py = side->starty;
  529.     if (inside_area(px, py)) {
  530.         notfirst = TRUE;
  531.         dist = distance(cx, cy, px, py);
  532.         /* Min separation default allows any min separation. */
  533.         if (dist < curmindistance)
  534.           return FALSE;
  535.         /* Default max separation says pos can never be too far away. */
  536.         if (curmaxdistance < 0 || dist < curmaxdistance)
  537.           toofar = FALSE;
  538.     }
  539.     }
  540.     if (toofar && notfirst)
  541.       return FALSE;
  542.     /* Count the types of terrain in the country. */
  543.     for_all_terrain_types(t)
  544.       numcells[t] = 0;
  545.     apply_to_area(cx, cy, tmpradius, count_cells);
  546.     /* Check against our upper and lower limits on terrain. */
  547.     for_all_terrain_types(t) {
  548.         if (numcells[t] < t_country_min(t))
  549.           return FALSE;
  550.     if (t_country_max(t) >= 0
  551.         && numcells[t] > t_country_max(t))
  552.       return FALSE;
  553.     }
  554.     return TRUE;
  555. }
  556.  
  557. /* Work hard to find a place for a side's country.  First make some random
  558.    trials, then start searching from the center of the area outwards.
  559.    Then just pick a place and plan to patch up the terrain later. */
  560.  
  561. static void
  562. find_a_place(side)
  563. Side *side;
  564. {
  565.     int tries, x, y, maxtries = area.numcells / 5;
  566.     Unit *unit;
  567.  
  568.     Dprintf("%s country ", side_desig(side));
  569.     /* First see if any of our units is already at a good location
  570.        to put the whole country. */
  571.     /* (should choose randomly from units first?) */
  572.     for_all_side_units(side, unit) {
  573.     if (in_play(unit) && good_place(unit->x, unit->y)) {
  574.         side->startx = unit->x;  side->starty = unit->y;
  575.         Dprintf("placed at unit %s\n", unit_desig(unit));
  576.         return;
  577.     }
  578.     }
  579.     /* Then try any of the independent units.  Probability of choosing
  580.        one is inversely proportional to the total number of units. */
  581.     for_all_side_units(indepside, unit) {
  582.     if (in_play(unit)
  583.         && good_place(unit->x, unit->y)
  584.         && probability(max(1, 100 / numunits))) {
  585.         side->startx = unit->x;  side->starty = unit->y;
  586.         Dprintf("placed at indep unit %s\n", unit_desig(unit));
  587.         return;
  588.     }
  589.     }
  590.     /* Then try some random locations. */
  591.     for (tries = 0; tries < maxtries; ++tries) {
  592.     if (tries % 10 == 0) {
  593.         announce_progress(sideprogress +
  594.                   ((sidedeltahalf / 2) * tries) / maxtries);
  595.     }
  596.     random_point(&x, &y);
  597.     /* Filter out points that are right on the edge.  If that's
  598.        where the only valid starting places are, the exhaustive
  599.        search will still find them. */
  600.     if (between(2, y, area.height - 2)
  601.         && between(2, x, area.width - 2)
  602.         && good_place(x, y)) { 
  603.         side->startx = x;  side->starty = y;
  604.         Dprintf("placed on try %d\n", tries);
  605.         return;
  606.     }
  607.     }
  608.     /* Then search exhaustively, starting from the center of the area. */
  609.     if (search_around(area.width / 2, area.halfheight,
  610.               area.width / 2 + area.halfheight,
  611.               good_place, &x, &y, 1)) {
  612.     side->startx = x;  side->starty = y;
  613.     Dprintf("placed after search\n");
  614.     return;
  615.     }
  616.     /* This should be a place in the area no matter what. */
  617.     random_point(&x, &y);
  618.     side->startx = x;  side->starty = y;
  619.     Dprintf("placed randomly\n");
  620.     ++badcountryplaces;
  621.     /* Since placement has become difficult, we get permission to alter
  622.        the terrain if necessary, while placing units. */
  623.     mungterrain = TRUE;
  624. }    
  625.  
  626. /* The basic conditions that *must* be met by an initial unit placement. */
  627.  
  628. static int
  629. valid_unit_place(x, y)
  630. int x, y;
  631. {
  632.     int t = terrain_at(x, y);
  633.  
  634.     return (inside_area(x, y)
  635.         && ut_favored(tmputype, t) > 0
  636.         && !ut_vanishes_on(tmputype, t)
  637.         && !ut_wrecks_on(tmputype, t)
  638.         && type_can_occupy_cell(tmputype, x, y));
  639. }
  640.  
  641. static int
  642. possible_unit_place(x, y)
  643. int x, y;
  644. {
  645.     return (inside_area(x, y) && unit_at(x, y) == NULL);
  646. }
  647.  
  648. /* Find a place somewhere in the designated area, following constraints
  649.    on terrain and adjacency.  Returns success of placement. */
  650.  
  651. static int
  652. find_unit_place(u, cx, cy, xp, yp)
  653. int u, cx, cy, *xp, *yp;
  654. {
  655.     int tries, x, y;
  656.     int maxtries = tmpradius * tmpradius * 5;
  657.  
  658.     Dprintf("%s place found ", u_type_name(u));
  659.     tmputype = u;
  660.     for (tries = 0; tries < maxtries; ++tries) {
  661.     if (random_point_near(cx, cy, tmpradius, &x, &y)) {
  662.         if (mungterrain
  663.             && !valid_unit_place(x, y)
  664.             && possible_unit_place(x, y)
  665.         && favorite[u] != NONTTYPE
  666.         && probability(ut_favored(u, favorite[u]))) {
  667.         Dprintf("(by munging) ");
  668.         mung_terrain(x, y, u);
  669.         }
  670.         if (valid_unit_place(x, y)
  671.             && probability(ut_favored(u, terrain_at(x, y)))) {
  672.             *xp = x;  *yp = y;
  673.         Dprintf("on try %d of %d\n", tries, maxtries);
  674.         return TRUE;
  675.         }
  676.     }
  677.     }
  678.     /* Random points aren't working, switch to exhaustive search. */
  679.     if (search_around(cx, cy, tmpradius, valid_unit_place, &x, &y, 1)) {
  680.     *xp = x;  *yp = y;
  681.     Dprintf("after search\n");
  682.     return TRUE;
  683.     }
  684.     /* Search again, just find a location that we can alter to suit. */
  685.     if (favorite[u] != NONTTYPE) {
  686.         if (search_around(cx, cy, tmpradius, possible_unit_place, &x, &y, 1)) {
  687.             mung_terrain(x, y, u);
  688.         *xp = x;  *yp = y;
  689.         Dprintf("(by munging) after search\n");
  690.         return TRUE;
  691.     }
  692.     }
  693.     Dprintf("- NOT!\n");
  694.     return FALSE;
  695. }
  696.  
  697. static void
  698. mung_terrain(x, y, u)
  699. int x, y, u;
  700. {
  701.     int dir, x1, y1;
  702.  
  703.     /* Alter the terrain to be compatible with the given unit type. */
  704.     set_terrain_at(x, y, favorite[u]);
  705.     /* Mung some empty adjacent cells also, improves appearance. */
  706.     for_all_directions(dir) {
  707.     if (interior_point_in_dir(x, y, dir, &x1, &y1)) {
  708.         if (unit_at(x1, y1) == NULL && flip_coin()) {
  709.         set_terrain_at(x1, y1, favorite[u]);
  710.         }
  711.     }
  712.     }
  713. }
  714.  
  715. static Unit *
  716. find_occupant_place(side, u, x0, y0)
  717. Side *side;
  718. int u, x0, y0;
  719. {
  720.     Unit *transport;
  721.  
  722.     /* (should cast about randomly first, then do full search) */
  723.     for_all_side_units(side, transport) {
  724.     if (is_unit(transport)
  725.         && inside_area(transport->x, transport->y)
  726.         && type_can_occupy(u, transport)) {
  727.         return transport;
  728.     }
  729.     }
  730.     /* (should be able to look at indep units in country) */
  731.     return NULL;
  732. }
  733.  
  734. static int
  735. at_country_units_max(side, u)
  736. Side *side;
  737. int u;
  738. {
  739.     int themax = u_country_units_max(u);
  740.  
  741.     if (themax < 0)
  742.       return FALSE;
  743.     /* (should adjust for advantage?) */
  744.     return (themax <= side->numunits[u]);
  745. }
  746.  
  747. /* A method that scatters independent units over the world. */
  748.  
  749. int
  750. make_independent_units(calls, runs)
  751. int calls, runs;
  752. {
  753.     int u, t, x, y;
  754.     int doindeptype[MAXUTYPES], doanytype = FALSE, doindeppeople = FALSE;
  755.     Unit *unit;
  756.  
  757.     /* Can't do anything without some terrain. */
  758.     if (!terrain_defined())
  759.       return FALSE;
  760.     /* Decide which types will be put down. */
  761.     for_all_unit_types(u) {
  762.         doindeptype[u] = FALSE;
  763.         for_all_terrain_types(t) {
  764.             if (ut_indep_density(u, t) > 0 && !ut_vanishes_on(u, t)) {
  765.                 doindeptype[u] = TRUE;
  766.                 doanytype = TRUE;
  767.                 break;
  768.             }
  769.         }
  770.     }
  771.     /* Make space for people sides if we're going to have any. */
  772.     if (!people_sides_defined()) {
  773.     for_all_terrain_types(t) {
  774.         if (t_indep_people(t) > 0)
  775.           doindeppeople = TRUE;
  776.     }
  777.     if (doindeppeople) {
  778.         allocate_area_people_sides();
  779.     }
  780.     }
  781.     /* If no units or peoples to do, don't waste time going through
  782.        the world. */
  783.     if (!doanytype && !doindeppeople)
  784.       return FALSE;
  785.     announce_lengthy_process("Making independents");
  786.     /* Now apply the process to each cell individually. */
  787.     for_all_interior_cells(x, y) {
  788.         /* Progress is approx proportional to "column" being worked on. */
  789.         if (y == 1 && x % 5 == 0)
  790.           announce_progress((x * 100) / area.width);
  791.     t = terrain_at(x, y);
  792.     for_all_unit_types(u) {
  793.         if (doindeptype[u]) {
  794.         if (ut_indep_density(u, t) > xrandom(10000)) {
  795.                 if (!ut_vanishes_on(u, t)
  796.             && type_can_occupy_cell(u, x, y)) {
  797.             unit = create_unit(u, TRUE);
  798.             if (unit != NULL) {
  799.                 init_supply(unit);
  800.                 enter_cell(unit, x, y);
  801.                 }
  802.             }
  803.         }
  804.         }
  805.     }
  806.     if (doindeppeople
  807.         /* Don't put indeps on top of people already on a side. */
  808.         && people_side_at(x, y) == NOBODY
  809.         && probability(t_indep_people(t))) {
  810.         /* 0 represents indep people present */
  811.         set_people_side_at(x, y, 0);
  812.     }
  813.     }
  814.     finish_lengthy_process();
  815.     return TRUE;
  816. }
  817.